This invention relates to document caching in proxy servers and, more particularly, to techniques for achieving improved cache performance by incorporating client session depth as a factor in a caching algorithm.
Local area networks in corporations, universities and other facilities are typically connected to a wide area network, known as the Internet, through a proxy server. The proxy server functions as an interface between multiple clients on the local area network and the Internet. Client requests are formatted by the proxy server and forwarded to the appropriate web server on the Internet. The requested information is returned to the client through the proxy server.
A file cache may be associated with the proxy server. The file cache is a device for storage of documents that are likely to be reused by clients on the local area network. The file cache may have the form of memory in the proxy server, a hard disk associated with the proxy server, or any other type of memory. When a requested document is present in the file cache, in can be retrieved with lower latency and at lower cost as compared with obtaining the same document from a remote web server. In addition, Internet traffic is reduced.
A critical factor in the effectiveness of a file cache is the algorithm or policy used for placing documents in the file cache. Clearly, a file cache is effective only if the documents contained in it are reused by the clients on the local area network, preferably multiple times. However, since it cannot be known in advance whether any particular document will be reused, caching policies rely upon predictions of document reuse.
There have been a number of studies that observed that the document access patterns in web servers and proxy servers follow a Zipf distribution in characteristics such as document access count and size. The observations indicate that there are a few xe2x80x9chotxe2x80x9d documents that are accessed repeatedly, and then there are a large number of documents that are accessed a few times.
This long-tailed nature of the access frequency of documents has led to many optimizations tailored to such distributions. Many cache replacement policies that optimize for document hit rate or byte-hit rate have been proposed.
Most studies comparing various caching algorithms on the Internet indicate that a size-aware greedy-dual algorithm works best for increasing document hit rate, while some frequency aware schemes work best for increasing byte-hit rate. A perfect Least Frequently Used (LFU) replacement scheme that has information about all documents accessed and their access count is considered to be the most effective for increasing byte-hit rates, but least practical of all replacement schemes, since it requires complete knowledge of all documents accessed, even if the document has been evicted from the cache. A more practical implementation of a frequency based scheme that keeps track of frequency of access of only documents currently in the file cache (in-cache LFU) does poorly compared to most other schemes and is a poor choice for replacement algorithms. In fact, of the more practically realizable solutions, a Least Recently Used (LRU) algorithm has been shown to be reasonably effective in increasing byte-hit rates, though it performs suboptimally in the case of document hit rates.
Despite extensive studies and analysis, document hit rates are typically below 50% in proxy servers, and the hit rates on smaller cache sizes are much lower. Accordingly, there is a need for improved techniques for operation of file caches in proxy servers.
In accordance with a first aspect of the invention, a method is provided for controlling document transfer in data communication apparatus for document transfer between a web server coupled to a wide area network and a client coupled to the wide area network. The method comprises the steps of monitoring the number of documents requested by a client in a current session, placing a document requested by the client in a file cache according to a caching algorithm that is based, at least in part, on the number of documents requested by the client in the current session, and accessing the document in the file cache when the document is requested subsequently by the client. The wide area network is typically the Internet.
The file cache is preferably associated with a proxy server that is coupled between the wide area network and a local area network that serves a plurality of clients. Alternatively, the file cache may be associated with a controller in a network element, such as a router or a bridge.
The caching algorithm for placing the document in the file cache preferably includes a function that decreases as the number of documents requested by the client in the(current session increases. The function may decrease continuously or in one or more steps as the number of documents requested by the client in the current session increases. In one embodiment, the function has a value of zero, i.e., the cache is bypassed, when the number of documents requested by the client in the current session exceeds a predetermined number. When the number of documents requested in the current session is less than or equal to the predetermined number, any desired caching algorithm may be utilized for placing the document in the file cache. The caching algorithm for placing the document in the file cache may incorporate a replacement algorithm, such as a size-based algorithm, a least recently used algorithm or a least frequently used algorithm.
The step of monitoring the number of documents requested may be performed across two or more web servers in the current session. In addition, the step of monitoring the number of documents requested may be performed across one or more timeouts in the current session.
According to another aspect of the invention, data communication apparatus is provided for coupling a local area network to a wide area network. The local area network interconnects a plurality of clients. The data communication apparatus comprises a file cache for storing documents requested by the clients from the wide area network, and a proxy server coupled between the local area network and the wide area network and coupled to the file cache. The proxy server comprises means for monitoring the number of documents requested by a client in a current session, means for placing a document requested by the client in the file cache according to a caching algorithm that is based, at least in part, on the number of documents requested by the client in the current session, and means for accessing the document in the file cache when the document is requested subsequently by one of the plurality of clients.